TNotes.leetcode

Appearance

0349. 两个数组的交集【简单】

0349. 两个数组的交集【简单】 ​

1. 📝 题目描述 ​

给定两个数组 nums1 和 nums2，返回 它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序。

示例 1：

txt
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

txt
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

2. 🎯 s.1 - 哈希集合法（推荐） ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 使用 Set 对两个数组去重
  const set1 = new Set(nums1)
  const set2 = new Set(nums2)

  // 存储交集结果
  const result = []

  // 查找交集元素
  for (const num of set1) {
    if (set2.has(num)) {
      result.push(num)
    }
  }

  return result
}
js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 使用 Set 对两个数组去重
  const set1 = new Set(nums1)
  const set2 = new Set(nums2)

  // 存储交集结果
  const result = []

  // 遍历较小的集合，提高效率
  const [smallerSet, largerSet] =
    set1.size < set2.size ? [set1, set2] : [set2, set1]

  // 查找交集元素
  for (const num of smallerSet) {
    if (largerSet.has(num)) {
      result.push(num)
    }
  }

  return result
}
  • 时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度
  • 空间复杂度：O(m+n)，需要存储两个集合
  • js-2 对遍历的次数进行了适当的优化。

3. 🎯 s.2 - 排序 + 双指针 ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 先对两个数组排序
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)

  const result = []
  let i = 0,
    j = 0

  // 使用双指针查找交集
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] < nums2[j]) {
      i++
    } else if (nums1[i] > nums2[j]) {
      j++
    } else {
      // 找到交集元素，注意：避免重复添加。
      if (result.length === 0 || result[result.length - 1] !== nums1[i]) {
        result.push(nums1[i])
      }
      i++
      j++
    }
  }

  return result
}
  • 时间复杂度：O(mlog⁡m+nlog⁡n)，主要是排序的时间复杂度
  • 空间复杂度：O(1)，不考虑输出数组

4. 🎯 s.3 - 使用内置方法（简洁但效率较低） ​

js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  // 使用 filter 和 includes 查找交集，然后用 Set 去重
  return [...new Set(nums1.filter((num) => nums2.includes(num)))]
}
  • 时间复杂度：O(m×n)，includes 操作需要线性时间
  • 空间复杂度：O(min(m,n))，Set 存储交集元素

Discussions